//给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任
//务。 
//
// 返回完成所有任务需要的 最少 轮数，如果无法完成所有任务，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 输入：tasks = [2,2,3,3,2,4,4,4,4,4]
//输出：4
//解释：要想完成所有任务，一个可能的计划是：
//- 第一轮，完成难度级别为 2 的 3 个任务。 
//- 第二轮，完成难度级别为 3 的 2 个任务。 
//- 第三轮，完成难度级别为 4 的 3 个任务。 
//- 第四轮，完成难度级别为 4 的 2 个任务。 
//可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。
// 
//
// 示例 2： 
//
// 输入：tasks = [2,3,3]
//输出：-1
//解释：难度级别为 2 的任务只有 1 个，但每一轮执行中，只能选择完成 2 个或者 3 个相同难度级别的任务。因此，无法完成所有任务，答案为 -1 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= tasks.length <= 10⁵ 
// 1 <= tasks[i] <= 10⁹ 
// 
//
// Related Topics 贪心 数组 哈希表 计数 👍 47 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2024-05-14 22:27:47
 * @description 2244.完成所有任务需要的最少轮数
 */
public class MinimumRoundsToCompleteAllTasks{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumRoundsToCompleteAllTasks fun=new MinimumRoundsToCompleteAllTasks();
	 	 Solution solution = fun.new Solution();
		  solution.minimumRounds(new int[]{2,2,3,3,2,4,4,4,4,4});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minimumRounds(int[] tasks) {
		int n = tasks.length;
		if(n==1) return -1;
		Arrays.sort(tasks);
		int[] ar = new int[tasks.length + 1];
		System.arraycopy(tasks,0,ar,0,n);
		ar[n]=-1;
		int t=0,count=0,i;
		int res=0;
		for ( i = 1; i < ar.length; i++) {
			if(ar[i]!=ar[t]){
				count=i-t;
				int mod=count%3;
				int cu=count/3;
				if(cu==0&&mod==1){
					return -1;
				}else if(mod!=0){
					res+=1;
				}
				res+=cu;
				t=i;
			}
		}
		return res;

    }

	public int minimumRounds1(int[] tasks) {
		Map<Integer, Integer> cnt = new HashMap<>();
		for (int t : tasks) {
			cnt.merge(t, 1, Integer::sum);
		}
		int ans = 0;
		for (int c : cnt.values()) {
			if (c == 1) {
				return -1;
			}
			ans += (c + 2) / 3;
		}
		return ans;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
